import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class project {
    public int minOperations(int[] nums) {
        int ret=0;
        int max=0;
        for(int num:nums){
            max=Math.max(max,num);
            while (num!=0){
                ret++;
                num=(num-1)&num;
            }
        }
        if(max!=0){
            while (max!=0){
                ret++;
                max/=2;
            }
            ret--;
        }
        return ret;
    }



















    int flag=1;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int row=grid1.length;
        int col=grid1[0].length;
        int ret=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid1[i][j]==1&&grid2[i][j]==1){
                    flag=1;
                    dfs(grid1,grid2,i,j,row,col);
                    ret+=flag;
                }
            }
        }
        return ret;
    }
    public void dfs(int[][] arr1,int[][] arr2,int x,int y,int row,int col){
        if(x<0||x>=row||y<0||y>=col||arr2[x][y]!=1){
            return;
        }
        arr2[x][y]=2;
        if(arr1[x][y]!=1){
            flag=0;
        }
        dfs(arr1,arr2,x+1,y,row,col);
        dfs(arr1,arr2,x-1,y,row,col);
        dfs(arr1,arr2,x,y+1,row,col);
        dfs(arr1,arr2,x,y-1,row,col);
    }




















    public int maxAreaOfIsland(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int max=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    int sum=dfs1(i,j,row,col,grid);
                    max=Math.max(max,sum);
                    grid[i][j]=0;
                }
            }
        }
        return max;
    }
    public int dfs1(int x,int y,int row,int col,int[][] arr){
        if(x<0||y<0||x>=row||y>=col||arr[x][y]==0){
            return 0;
        }
        int sum=1;
        arr[x][y]=0;
        sum+=dfs1(x-1,y,row,col,arr);
        sum+=dfs1(x+1,y,row,col,arr);
        sum+=dfs1(x,y-1,row,col,arr);
        sum+=dfs1(x,y+1,row,col,arr);
        return sum;
    }













    public List<Integer> maxScoreIndices(int[] nums) {
        List<Integer> list=new ArrayList<>();
        int len=nums.length;
        int[] arr0=new int[len+1];
        int[] arr1=new int[len+1];
        for(int i=1;i<=len;i++){
            arr0[i]=nums[i-1]==0?arr0[i-1]+1:arr0[i-1];
        }
        for(int i=len-1;i>=0;i--){
            arr1[i]=nums[i]==1?arr1[i+1]+1:arr1[i+1];
        }
        int max=0;
        for(int i=0;i<=len;i++){
            max=Math.max(max,arr0[i]+arr1[i]);
        }
        for(int i=0;i<=len;i++){
            if(max==arr0[i]+arr1[i]){
                list.add(i);
            }
        }
        return list;
    }





















    public int uniqueMorseRepresentations(String[] words) {
        String[] str={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> set=new HashSet<>();
        for(String s:words){
            char[] ch=s.toCharArray();
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<ch.length;i++){
                int index=ch[i]-'a';
                sb.append(str[index]);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}
